class Solution {
public:
    int calculate(string s) {
        //1.去空格
        //2.处理负数
        hash['*']=hash['/']=2;
        hash['-']=hash['+']=1;
        string t;
        for(auto e:s)
        {
            if(e!=' ')
            {
                t+=e;
            }
        }
        string m;
        for(int i=0;i<t.size();i++)
        {
            if(t[i]=='-' &&(i==0 ||t[i-1]=='('))
            {
                m+="0-";
            }
            else
            {
                m+=t[i];
            }
        }
        vector<string> ret;
        int index=0;
        dfs(m,index,ret);
        stack<int> st;
        for(auto& e:ret)
        {
            if(e=="*" || e=="/" ||e=="-"|| e=="+")
            {
                int t1=st.top();st.pop();
                int t2=st.top();st.pop();
                if(e=="*")
                {
                    st.push(t1*t2);
                }
                else if(e=="/")
                {
                    st.push(t2/t1);
                }
                else if(e=="+")
                {
                    st.push(t2+t1);
                }
                else 
                {
                    st.push(t2-t1);
                }

            }
            else
            {
                st.push(stoi(e));
            }
        }
        return st.top();
        
    }
    unordered_map<char,int> hash;
    void dfs(string& m,int & index,vector<string> &ret)
    {
        stack<char> st;
        while(index<m.size())
        {
            if(isdigit(m[index]))
            {
                string t;
                while(index<m.size()&&isdigit(m[index]))
                {
                    t+=m[index++];
                }
                ret.push_back(t);//如果是数直接进后缀表达式
            }
            else if(m[index]=='(')
            {
                index++;
                dfs(m,index,ret);
            }
            else if(m[index]==')')
            {
                while(!st.empty())
                {
                    ret.push_back(string(1,st.top()));
                    st.pop();
                }
                index++;
                return;

            }
            else
            {
                if(st.empty() ||hash[st.top()]<hash[m[index]])
                {
                    st.push(m[index]);
                }
                else
                {
                    while(!st.empty() &&hash[m[index]]<=hash[st.top()])
                    {
                        ret.push_back(string(1,st.top()));
                        st.pop();
                    }
                    st.push(m[index]);
                }
                index++;


            }
        }

        while(!st.empty())
        {
            ret.push_back(string(1,st.top()));
            st.pop();
        }
        


    }
};